package com.mdnote.practice.tire;

import org.junit.Assert;
import org.junit.Test;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/11/15 10:24
 * @Email rhythm_2019@163.com
 * @Description 316. 去除重复字母
 */
public class LeetCode316 {

    public String removeDuplicateLetters(String s) {
        HashMap<Character, Integer> lastSeebIdxMap = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            lastSeebIdxMap.put(s.charAt(i), i);
        }

        HashSet<Character> seen = new HashSet<>();
        LinkedList<Character> deueu = new LinkedList<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (seen.contains(c)) {
                // 去重
                continue;
            }
            // 栈不为空、栈内元素字典序比当前玄素大且该字符后面还会出现
            while (!deueu.isEmpty() && deueu.peekLast() > c && lastSeebIdxMap.get(deueu.peekLast()) > i) {
                seen.remove(deueu.pollLast());
            }
            seen.add(c);
            deueu.offerLast(c);
        }

        StringBuilder stringBuilder = new StringBuilder();
        while (!deueu.isEmpty()) {
            stringBuilder.append(deueu.pollFirst());
        }

        return stringBuilder.toString();

    }

    @Test
    public void test_01() {
        LeetCode316 leetCode316 = new LeetCode316();
        Assert.assertEquals(leetCode316.removeDuplicateLetters("bcabc"), "abc");
        Assert.assertEquals(leetCode316.removeDuplicateLetters("cbacdcbc"), "acdb");
    }
}
